package algorithm.poj.p2000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLDecoder;
import java.util.StringTokenizer;


/**
 * 分析：
 *    
 * 实现：
 * 
 * 经验：
 * 
 * 教训：
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P2696 {

	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P2696.class.getResource("P2696.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));
		
		String line = stdin.readLine();
		int n = Integer.valueOf(line.trim());
		for (int j = 0; j < n; j ++) {
			StringTokenizer st = new StringTokenizer(stdin.readLine());
			int a = Integer.valueOf(st.nextToken());
			int b = Integer.valueOf(st.nextToken());
			int c = Integer.valueOf(st.nextToken());
			int d = Integer.valueOf(st.nextToken());
			int e = Integer.valueOf(st.nextToken());
			int f = Integer.valueOf(st.nextToken());
			int g = Integer.valueOf(st.nextToken());
			int h = Integer.valueOf(st.nextToken());
			int i = Integer.valueOf(st.nextToken());
			System.out.println(phi(a,b,c,d,e,f,g,h,i));
		}
	}

	private static int phi(int a, int b, int c, 
			int d, int e, int f, int g, int h, int i) {
		
		if (i == 0) return a;
		else if (i == 1) return b;
		else if (i == 2) return c;
		else {
			int x = a;
			int y = b;
			int z = c;
			int t = -1;
			for (int k = 0; k < i-2; k ++) {
				if (k%2 == 0) {
					t = (d*z + e*y - f*x)%g;
					if (t < 0) t += g;
				} else {
					t = (f*z - d*y + e*x)%h;
					if (t < 0) t += h;
				}
				x = y;
				y = z;
				z = t;
			}
			return t;
		}
	}
}
